home *** CD-ROM | disk | FTP | other *** search
/ Aminet 12 / Aminet 12 (1996)(GTI - Schatztruhe)[!][Jun 1996].iso / Aminet / dev / e / framework.lha / fw / sortedTree.e < prev    next >
Encoding:
Text File  |  1996-01-28  |  3.0 KB  |  124 lines
  1.  
  2. -> sortedTree is an efficient data structure for comparable objects.
  3. -> Time complexity for data adding is O(log n).
  4. -> Space complexity is O(n).
  5.  
  6. -> Copyright © Guichard Damien 01/04/1996
  7.  
  8. OPT MODULE
  9. OPT EXPORT
  10. OPT NOWARN
  11.  
  12. MODULE 'fw/comparable'
  13.  
  14. OBJECT sortedTree OF comparable
  15.   left:PTR TO sortedTree
  16.   right:PTR TO sortedTree
  17. ENDOBJECT
  18.  
  19. -> Count nodes.
  20. PROC nodes() OF sortedTree
  21.   DEF tot=1
  22.   IF self.left  THEN tot:=tot+self.left.nodes()
  23.   IF self.right THEN tot:=tot+self.right.nodes()
  24. ENDPROC tot
  25.  
  26. -> Count leaves.
  27. PROC leaves() OF sortedTree
  28.   DEF tot=0
  29.   IF self.left THEN tot:=tot+self.left.leaves()
  30.   IF self.right
  31.     tot:=tot+self.right.leaves()
  32.   ELSEIF self.left=NIL  -> Both NIL, so a leaf
  33.     tot++
  34.   ENDIF
  35. ENDPROC tot
  36.  
  37. -> Add an element to the tree.
  38. PROC add(e:PTR TO sortedTree) OF sortedTree
  39.   DEF parent:PTR TO sortedTree
  40.   WHILE self
  41.     parent:=self
  42.     self:=IF e.isLessThan(self) THEN self.left ELSE self.right
  43.   ENDWHILE
  44.   IF e.isLessThan(parent)
  45.     parent.left:=e
  46.   ELSE
  47.     parent.right:=e
  48.   ENDIF
  49. ENDPROC
  50.  
  51. -> Print the tree in infix order.
  52. PROC printNodes() OF sortedTree
  53.   IF self.left  THEN self.left.printNodes()
  54.   self.out()
  55.   IF self.right THEN self.right.printNodes()
  56. ENDPROC
  57.  
  58. -> Print tree leaves from left to right.
  59. PROC printLeaves() OF sortedTree
  60.   IF self.left THEN self.left.printLeaves()
  61.   IF self.right
  62.     self.right.printLeaves()
  63.   ELSEIF self.left=NIL  -> Both NIL, so a leaf
  64.     self.out()
  65.   ENDIF
  66. ENDPROC
  67.  
  68. -> Tree performance expressed in percentage of the 
  69. -> performance of a perfectly balanced binary tree.
  70. PROC performance() OF sortedTree
  71.   DEF count,weight=0,number=1
  72.   DEF best=0,actual
  73.   count:=self.nodes()
  74.   WHILE count>number
  75.     best:=number*weight+best
  76.     count:=count-number
  77.     INC weight
  78.     number:=number*2
  79.   ENDWHILE
  80.   best:=count*weight+best     -> Length of a walk in a perfect tree
  81.   actual:=self.walkLength(0)  -> Length of a walk in the real tree
  82. ENDPROC best*100/actual       -> performance in %
  83.  
  84. -> Lenght of a walk in the tree.
  85. PROC walkLength(depth) OF sortedTree
  86.   DEF tot=0
  87.   IF self.left  THEN tot:=tot+self.left.walkLength(depth+1)
  88.   IF self.right THEN tot:=tot+self.right.walkLength(depth+1)
  89. ENDPROC depth+tot
  90.  
  91. -> Prefix walk through the tree.
  92. PROC prefix(proc) OF sortedTree
  93.   proc(self)
  94.   IF self.left  THEN self.left.prefix(proc)
  95.   IF self.right THEN self.right.prefix(proc)
  96. ENDPROC
  97.  
  98. -> Infix walk through the tree.
  99. PROC infix(proc) OF sortedTree
  100.   proc(self)
  101.   IF self.left  THEN self.left.infix(proc)
  102.   IF self.right THEN self.right.infix(proc)
  103. ENDPROC
  104.  
  105. -> Postfix walk through the tree.
  106. PROC postfix(proc) OF sortedTree
  107.   proc(self)
  108.   IF self.left  THEN self.left.postfix(proc)
  109.   IF self.right THEN self.right.postfix(proc)
  110. ENDPROC
  111.  
  112. -> NEVER call this method. Use loadObject() instead.
  113. PROC load() OF sortedTree
  114.   IF self.left  THEN self.left :=self.loadObject()
  115.   IF self.right THEN self.right:=self.loadObject()
  116. ENDPROC
  117.  
  118. -> NEVER call this method. Use storeObject() instead.
  119. PROC store() OF sortedTree
  120.   IF self.left  THEN self.left.storeObject()
  121.   IF self.right THEN self.right.storeObject()
  122. ENDPROC
  123.  
  124.